package jianzhi

func lowestCommonAncestor1(root, p, q *TreeNode) *TreeNode {
	if root == nil || p == nil || q == nil {
		return nil
	}

	if root.Val == p.Val {
		return p
	} else if root.Val == q.Val {
		return q
	}

	if root.Val > p.Val && root.Val > q.Val {
		return lowestCommonAncestor1(root.Left, p, q)
	}

	if root.Val < p.Val && root.Val < q.Val {
		return lowestCommonAncestor1(root.Right, p, q)
	}

	return root

}
